/**
 * 
 */
package edu.hit.irlab.coref.evaluation.methds;

import java.util.ArrayList;
import edu.hit.irlab.coref.evaluation.PRScoreStruct;;

/**
 * the CEAF evaluate algorithm
 * @author langjun, modified by chuter
 */

class HungarianAlgorithm {	
	   //*******************************************//
	   //METHODS THAT PERFORM ARRAY-PROCESSING TASKS//
	   //*******************************************//

	   //Finds the largest element in a positive array.
	   public static double findLargest (double[][] array) {
	      //works for arrays where all values are >= 0.
	      double largest = 0;
	      for (int i=0; i<array.length; i++) {
	         for (int j=0; j<array[i].length; j++) {
	            if (array[i][j] > largest)
	               largest = array[i][j];
	         }
	      }
	      return largest;
	   }

	   //Transposes a double[][] array.
	   public static double[][] transpose (double[][] array) {
	      double[][] transposedArray = new double[array[0].length][array.length];
	      for (int i=0; i<transposedArray.length; i++) {
	         for (int j=0; j<transposedArray[i].length; j++)
	            transposedArray[i][j] = array[j][i];
	      }
	      return transposedArray;
	   }

	   //Copies all elements of an array to a new array.
	   public static double[][] copyOf (double[][] original) {
	      double[][] copy = new double[original.length][original[0].length];
	      for (int i=0; i<original.length; i++) {
	         //Need to do it this way, otherwise it copies only memory location
	         System.arraycopy(original[i], 0, copy[i], 0, original[i].length);
	      }
	      return copy;
	   }

	   //**********************************//
	   //METHODS OF THE HUNGARIAN ALGORITHM//
	   //**********************************//

	   public static int[][] hgAlgorithm (double[][] array, String sumType) {
	      double[][] cost = copyOf(array);	//Create the cost matrix
	      //Then array is weight array. Must change to cost.
	      if (sumType.equalsIgnoreCase("max")) {
	         double maxWeight = findLargest(cost);
	         //Generate cost by subtracting.
	         for (int i=0; i<cost.length; i++) {
	            for (int j=0; j<cost[i].length; j++)
	               cost [i][j] = (maxWeight - cost [i][j]);
	         }
	      }
	      double maxCost = findLargest(cost);		    //Find largest cost matrix element (needed for step 6).

	      int[][] mask = new int[cost.length][cost[0].length];  //The mask array.
	      int[] rowCover = new int[cost.length];		    //The row covering vector.
	      int[] colCover = new int[cost[0].length];		    //The column covering vector.
	      int[] zero_RC = new int[2];                           //Position of last zero from Step 4.
	      int step = 1;											
	      boolean done = false;
	      //main execution loop
	      while (done == false) { 
	         switch (step) {
	            case 1:
	               step = hg_step1(step, cost);     
	               break;
	            case 2:
	               step = hg_step2(step, cost, mask, rowCover, colCover);
	               break;
	            case 3:
	               step = hg_step3(step, mask, colCover);
	               break;
	            case 4:
	               step = hg_step4(step, cost, mask, rowCover, colCover, zero_RC);
	               break;
	            case 5:
	               step = hg_step5(step, mask, rowCover, colCover, zero_RC);
	               break;
	            case 6:
	               step = hg_step6(step, cost, rowCover, colCover, maxCost);
	               break;
	            case 7:
	               done=true;
	               break;
	         }
	      }//end while

	      int[][] assignment = new int[array.length][2];	//Create the returned array.
	      for (int i=0; i<mask.length; i++) {
	         for (int j=0; j<mask[i].length; j++) {
	            if (mask[i][j] == 1) {
	               assignment[i][0] = i;
	               assignment[i][1] = j;
	            }
	         }
	      }
	      //If you want to return the min or max sum, in your own main method
	      //instead of the assignment array, then use the following code:
	      /*
	         double sum = 0; 
	         for (int i=0; i<assignment.length; i++)
	         {
	         sum = sum + array[assignment[i][0]][assignment[i][1]];
	         }
	         return sum;
	       */
	      //Of course you must also change the header of the method to:
	      //public static double hgAlgorithm (double[][] array, String sumType)
	      return assignment;
	   }

	   public static int hg_step1(int step, double[][] cost) {
	      //What STEP 1 does:
	      //For each row of the cost matrix, find the smallest element
	      //and subtract it from from every other element in its row. 

	      double minval;
	      for (int i=0; i<cost.length; i++) {									
	         minval=cost[i][0];
	         //1st inner loop finds min val in row.
	         for (int j=0; j<cost[i].length; j++) {
	            if (minval>cost[i][j])
	               minval=cost[i][j];
	         }
	         for (int j=0; j<cost[i].length; j++)	//2nd inner loop subtracts it.
	            cost[i][j]=cost[i][j]-minval;
	      }
	      step=2;
	      return step;
	   }

	   public static int hg_step2 (int step, double[][] cost, int[][] mask, int[]rowCover, int[] colCover) {
	      //What STEP 2 does:
	      //Marks uncovered zeros as starred and covers their row and column.
	      for (int i=0; i<cost.length; i++) {
	         for (int j=0; j<cost[i].length; j++) {
	            if ((cost[i][j]==0) && (colCover[j]==0) && (rowCover[i]==0)) {
	               mask[i][j]=1;
	               colCover[j]=1;
	               rowCover[i]=1;
	            }
	         }
	      }
	      clearCovers(rowCover, colCover);	//Reset cover vectors.
	      step=3;
	      return step;
	   }
	   public static int hg_step3 (int step, int[][] mask, int[] colCover) {
	      //What STEP 3 does:
	      //Cover columns of starred zeros. Check if all columns are covered.

	      //Cover columns of starred zeros.
	      for (int i=0; i<mask.length; i++) {
	         for (int j=0; j<mask[i].length; j++) {
	            if (mask[i][j] == 1)
	               colCover[j]=1;
	         }
	      }
	      int count=0;						
	      for (int j=0; j<colCover.length; j++)	//Check if all columns are covered.
	         count=count+colCover[j];
	      if (count>=mask.length)	//Should be cost.length but ok, because mask has same dimensions.	
	         step=7;
	      else
	         step=4;
	      return step;
	   }

	   public static int hg_step4 (int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC) {
	      //What STEP 4 does:
	      //Find an uncovered zero in cost and prime it (if none go to step 6). Check for star in same row:
	      //if yes, cover the row and uncover the star's column. Repeat until no uncovered zeros are left
	      //and go to step 6. If not, save location of primed zero and go to step 5.

	      int[] row_col = new int[2];	//Holds row and col of uncovered zero.
	      boolean done = false;
	      while (done == false) {
	         row_col = findUncoveredZero(row_col, cost, rowCover, colCover);
	         if (row_col[0] == -1) {
	            done = true;
	            step = 6;
	         }
	         else {
	            mask[row_col[0]][row_col[1]] = 2;	//Prime the found uncovered zero.
	            boolean starInRow = false;
	            for (int j=0; j<mask[row_col[0]].length; j++) {
	               //If there is a star in the same row...
	               if (mask[row_col[0]][j]==1) {
	                  starInRow = true;
	                  //remember its column.
	                  row_col[1] = j;
	               }
	            }

	            if (starInRow==true) {
	               rowCover[row_col[0]] = 1;	//Cover the star's row.
	               colCover[row_col[1]] = 0;	//Uncover its column.
	            }
	            else {
	               zero_RC[0] = row_col[0];	        //Save row of primed zero.
	               zero_RC[1] = row_col[1];	        //Save column of primed zero.
	               done = true;
	               step = 5;
	            }
	         }
	      }
	      return step;
	   }

	   //Aux 1 for hg_step4.
	   public static int[] findUncoveredZero (int[] row_col, double[][] cost, int[] rowCover, int[] colCover) {
	      row_col[0] = -1;	//Just a check value. Not a real index.
	      row_col[1] = 0;

	      int i = 0; boolean done = false;
	      while (done == false) {
	         int j = 0;
	         while (j < cost[i].length) {
	            if (cost[i][j]==0 && rowCover[i]==0 && colCover[j]==0) {
	               row_col[0] = i;
	               row_col[1] = j;
	               done = true;
	            }
	            j = j+1;
	         }//end inner while
	         i=i+1;
	         if (i >= cost.length)
	            done = true;
	      }//end outer while
	      return row_col;
	   }

	   public static int hg_step5 (int step, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC) {
	      //What STEP 5 does:	
	      //Construct series of alternating primes and stars. Start with prime from step 4.
	      //Take star in the same column. Next take prime in the same row as the star. Finish
	      //at a prime with no star in its column. Unstar all stars and star the primes of the
	      //series. Erasy any other primes. Reset covers. Go to step 3.

	      int count = 0;					       //Counts rows of the path matrix.
	      int[][] path = new int[(mask[0].length*mask.length)][2]; //Path matrix (stores row and col).
	      path[count][0] = zero_RC[0];			       //Row of last prime.
	      path[count][1] = zero_RC[1];			       //Column of last prime.

	      boolean done = false;
	      while (done == false) { 
	         int r = findStarInCol(mask, path[count][1]);
	         if (r>=0) {
	            count = count+1;
	            path[count][0] = r;			//Row of starred zero.
	            path[count][1] = path[count-1][1];	//Column of starred zero.
	         }
	         else
	            done = true;

	         if (done == false) {
	            int c = findPrimeInRow(mask, path[count][0]);
	            count = count+1;
	            path[count][0] = path [count-1][0];	//Row of primed zero.
	            path[count][1] = c;			//Col of primed zero.
	         }
	      }//end while

	      convertPath(mask, path, count);
	      clearCovers(rowCover, colCover);
	      erasePrimes(mask);

	      step = 3;
	      return step;

	   }

	   //Aux 1 for hg_step5.
	   public static int findStarInCol (int[][] mask, int col) {
	      int r=-1;	//Again this is a check value.
	      for (int i=0; i<mask.length; i++) {
	         if (mask[i][col]==1)
	            r = i;
	      }
	      return r;
	   }

	   //Aux 2 for hg_step5.
	   public static int findPrimeInRow (int[][] mask, int row) {
	      int c = -1;
	      for (int j=0; j<mask[row].length; j++) {
	         if (mask[row][j]==2)
	            c = j;
	      }
	      return c;
	   }

	   //Aux 3 for hg_step5.
	   public static void convertPath (int[][] mask, int[][] path, int count) {
	      for (int i=0; i<=count; i++) {
	         if (mask[(path[i][0])][(path[i][1])]==1)
	            mask[(path[i][0])][(path[i][1])] = 0;
	         else
	            mask[(path[i][0])][(path[i][1])] = 1;
	      }
	   }

	   //Aux 4 for hg_step5.
	   public static void erasePrimes (int[][] mask) {
	      for (int i=0; i<mask.length; i++) {
	         for (int j=0; j<mask[i].length; j++) {
	            if (mask[i][j]==2)
	               mask[i][j] = 0;
	         }
	      }
	   }

	   //Aux 5 for hg_step5 (and not only).
	   public static void clearCovers (int[] rowCover, int[] colCover) {
	      for (int i=0; i<rowCover.length; i++)
	         rowCover[i] = 0;
	      for (int j=0; j<colCover.length; j++)
	         colCover[j] = 0;
	   }

	   public static int hg_step6 (int step, double[][] cost, int[] rowCover, int[] colCover, double maxCost) {
	      //What STEP 6 does:
	      //Find smallest uncovered value in cost: a. Add it to every element of covered rows
	      //b. Subtract it from every element of uncovered columns. Go to step 4.
	      double minval = findSmallest(cost, rowCover, colCover, maxCost);
	      for (int i=0; i<rowCover.length; i++) {
	         for (int j=0; j<colCover.length; j++) {
	            if (rowCover[i]==1)
	               cost[i][j] = cost[i][j] + minval;
	            if (colCover[j]==0)
	               cost[i][j] = cost[i][j] - minval;
	         }
	      }
	      step = 4;
	      return step;
	   }


	   //Aux 1 for hg_step6.
	   public static double findSmallest (double[][] cost, int[] rowCover, int[] colCover, double maxCost) {
	      //There cannot be a larger cost than this.
	      double minval = maxCost;				
	      //Now find the smallest uncovered value.
	      for (int i=0; i<cost.length; i++) {	
	         for (int j=0; j<cost[i].length; j++) {
	            if (rowCover[i]==0 && colCover[j]==0 && (minval > cost[i][j]))
	               minval = cost[i][j];
	         }
	      }
	      return minval;
	   }
}

/**
 * The Class Ceaf.
 * This class define a algorithm developed by Luo Xiaoqiang called CEAF
 */
public class Ceaf {
	private static double[][] matrix1;
	private static double[][] matrix2;
	private static double[][] matrix1_rev;
	private static double[][] matrix2_rev;
	private static int groups_res = 0;
	private static int groups_key = 0;
	private static int num_res = 0;
	private static int num_key = 0;
	private static int rk = 0;
	
	private static void clean() {
		matrix1 = null;
		matrix2 = null;
		matrix1_rev = null;
		matrix2_rev = null;
		groups_res = 0;
		groups_key = 0;
		num_res = 0;
		num_key = 0;
		rk = 0;
	}
	
	private static int common(ArrayList<Integer> r, ArrayList<Integer> c) {
		int rtn = 0;
		
		for (Integer num : r) {
			if (c.contains(num)) {
				rtn += 1;
			}
		}
		
		return rtn;
	}
	
	private static void make_matrix(
			ArrayList<ArrayList<Integer>> entityMentionsMatchKey,
			ArrayList<ArrayList<Integer>> entityMentionsMatchRes
		) {
		int row = entityMentionsMatchRes.size();
		int col = entityMentionsMatchKey.size();
		groups_res = row;
		groups_key = col;
		
		int s = Math.max(row, col);
		
		//double[][] transposedArray = new double[array[0].length][array.length];
		matrix1 = new double[row][col];
		matrix2 = new double[row][col];
		matrix1_rev = new double[row][col];
		matrix2_rev = new double[row][col];
		
		for (ArrayList<Integer> r : entityMentionsMatchRes)
			num_res += r.size();
		
		for (ArrayList<Integer> k : entityMentionsMatchKey)
			num_key += k.size();
		
		for (int r = 0; r < row; r++) {
			for (int c = 0; c < col; c++) {
				double common = common(entityMentionsMatchRes.get(r), 
						entityMentionsMatchKey.get(c));
				double commondivided = 2 * common / (entityMentionsMatchRes.get(r).size()
						+ entityMentionsMatchKey.get(c).size()); 
				matrix1[r][c] = common;
				matrix2[r][c] = commondivided;
				matrix1_rev[r][c] = Integer.MAX_VALUE - common;
				matrix2_rev[r][c] = Integer.MAX_VALUE - commondivided;
			}
		}
		
		if (matrix1.length > matrix1[0].length) {
	         //System.out.println("Array transposed (because rows>columns).\n");	//Cols must be >= Rows.
	         matrix1 = HungarianAlgorithm.transpose(matrix1);
		}
		if (matrix2.length > matrix2[0].length) {
	         //System.out.println("Array transposed (because rows>columns).\n");	//Cols must be >= Rows.
	         matrix2 = HungarianAlgorithm.transpose(matrix2);
		}
		
	}
	
	public static PRScoreStruct CeafScore(int mode,
			ArrayList<ArrayList<Integer>> entityMentionsMatchKey,
			ArrayList<ArrayList<Integer>> entityMentionsMatchRes
		) {
		CeafScore score = scorePart(mode, entityMentionsMatchKey, entityMentionsMatchRes);
		return new PRScoreStruct(score.above/score.pBelow, score.above/score.rBelow);
	}
	
	public static CeafScore scorePart(int mode,
			ArrayList<ArrayList<Integer>> entityMentionsMatchKey,
			ArrayList<ArrayList<Integer>> entityMentionsMatchRes
		) {
		clean();
		
		//Below enter "max" or "min" to find maximum sum or minimum sum assignment.
	    String sumType = "max";
		
	    make_matrix(entityMentionsMatchKey, entityMentionsMatchRes);
	    
		ArrayList<Double> rtnBcubedScores = new ArrayList<Double>();
		
		HungarianAlgorithm m = new HungarianAlgorithm();
		
	    double total = 0;
	    double recallUnder = 0;
	    double preciseUnder = 0;
	
	    if (mode == 1) {
	    	int[][] assignment = new int[matrix1.length][2];
	    	assignment = m.hgAlgorithm(matrix1, sumType);	//Call Hungarian algorithm.
	    	for (int r = 0; r < assignment.length; r++) {
	    		total += matrix1[assignment[r][0]][assignment[r][1]];
	    	}
	    	recallUnder =  num_key;
	    	preciseUnder = num_res;
	    } else if (mode == 2) {
	    	int[][] assignment = new int[matrix2.length][2];
	    	assignment = m.hgAlgorithm(matrix2, sumType);	//Call Hungarian algorithm.
	    	for (int r = 0; r < assignment.length; r++) {
	    		total += matrix2[assignment[r][0]][assignment[r][1]];
	    	}
	    	recallUnder = groups_key;
	    	preciseUnder = groups_res;
	    }
	    
	    return new CeafScore(total, preciseUnder, recallUnder);
	}
	
	public static class CeafScore {
		public double above;
		public double pBelow;
		public double rBelow;
		public CeafScore(double above, double pBelow, double rBelow) {
			this.above = above;
			this.pBelow = pBelow;
			this.rBelow = rBelow;
		}
		//add two score_parts
		public void add(CeafScore anotherScore) {
			above += anotherScore.above;
			pBelow += anotherScore.pBelow;
			rBelow += anotherScore.rBelow;
		}
		//convert to PRScore
		public PRScoreStruct toPRScore() {
			//P=above/pBelow, R=above/pBelow
			return new PRScoreStruct(above/pBelow, above/rBelow);
		}
	}
	
}
